COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	~[C<NαWINGED EDGE.
C00005 00003	~H7O0,630,750
C00007 00004	[2.1	Winged Edge Link Fields.]
C00012 00005	
C00015 00006	[2.2	Perimeter Accessing.]
C00021 00007	[2.3	Edge and Face Splitting.]
C00023 00008	
C00025 00009	[2.4	Lowest Level Polyhedron Synthesis and Alteration.]
C00027 00010		In the  typical situation, there  are five steps:  first, get
C00030 00011	[2.5	Coordinate Free Polyhedron Representation.]
C00033 ENDMK
C⊗;
~[C;<N;αWINGED EDGE.;
~λ30;I425,0;P10;JCFA           SECTION 2.
~JCFD          THE WINGED EDGE POLYHEDRON REPRESENTATION.

~I950,0;FC2.0	Introduction to the Winged Edge.
~JUFA
	In this  chapter,  a  particular computer  representation for
polyhedra  is presented and  some of  its virtues are  explained. The
representation is implemented as  a data structure composed of  small
blocks of words containing pointers and  data in the fashion usual to
graphics  and simulation. An  introduction to data  structures can be
found in Knuth  (Art of Computer  Programming, chapter 2, volume  I).
Quickly  reviewing   Knuth's  terminology:  a  node  is   a  group  of
consecutive words of memory, a field is a named portion of a node and
a link is  the absolute machine address  of a node. The  notation for
referring  to a  field of a  node consists  simply of the  field name
followed by a  link expression enclosed  in parentheses. For  example,
the two faces of an edge node  whoes link is stored in the variable named
"edge", are found in the fields named NFACE and PFACE, and are referred
to as NFACE(edge) and  PFACE(edge).  Although the latest  language of
implementation is  PDP-10 machine code, examples will be given in a
fictional programming language which combines ALGOL
with Knuthian node/link notation.~Q;F.
~H7;O0,630,750;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;

L-30,-10;FBedge~
L-380,-10;FBNFACE(edge)~
L240,-10;FBPFACE(edge)~

L-70,-370;FBNVT(edge)~
L-70,350;FBPVT(edge)~

L-360,320;FBNCCW(edge)~
L-390,-360;FBNCW(edge)~
L220,320;FBPCW(edge)~
L260,-360;FBPCCW(edge)~

I1350,0;O0,630,950;
λ10;JC;FA[FIGURE 2.1 - Winged Edge Topology]

The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
	NFACE(edge)	Negative Face of edge.
	PFACE(edge)	Positive Face of edge.
	PVT(edge)		Positive Vertex of edge.
	NVT(edge)		Negative Vertex of edge.
	NCW(edge)		edge in Negative face Clockwise from edge.
	PCW(edge)		edge in Positive face Clockwise from edge.
	NCCW(edge)		edge in Negative face Counter Clockwise from edge.
	PCCW(edge)		edge in Positive face Counter Clockwise from edge.
~λ30;Q;FA
[2.1	Winged Edge Link Fields.]

	A polyhedron  in  made up  of four  kinds  of nodes:  bodies,
faces, edges and  vertices. The body node is the head of three rings:
a ring of faces, a  ring of edges and  a ring of vertices. Each  face
and each  vertex points at  one of the  edges on its  perimeter. Each
edge  points at its  two faces  and its two  vertices. Completing the
topology, each  edge  node  contains a  link  to  each of  its  four
immediate  neighboring edges clockwise  and counter  clockwise around
face perimeters (as seen from the exterior side of the surface of the
polyhedron). These last four links are the wings  of the edge,  which
provide the basis  for efficient face and vertex perimeter accessing.
Finally,  the links  of the edge  nodes can be consistently  oriented
with respect  to the surface  of the  polyhedron so that  the surface
always has two sides: the inside and the outside.

	Observe that there are twenty-two  link fields in  the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten  links. Thus the least number of  different
link field names  that need to be  coined is ten; if we  allow a link
name  such as PED  to serve  different roles depending  on whether it
applies to a body, face, edge or vertex. The  data structures and the
link fields comprising the structures are listed in box (2.1) below.
The ten links  names include:  NFACE and  PFACE for  two fields  that
contain face links  in edges and the face  ring, NED and PED  for two
fields  that contain  edge links,  NVT  and PVT  for two  fields that
contain vertex links, and NCW, PCW, NCCW and PCCW for the four fields
that contain edge links and are called the wings.

~|--------------------------------------------------------------λ10;JAFA
BOX 2.1    Data Structure			Link Names

	1. Face Ring of a Body.			NFACE	PFACE
	2. Edge Ring of a Body.			NED		PED
	3. Vertex Ring of a Body.			NVT		PVT
	4. First Edge of a Vertex.				PED
	5. First Edge of a Face.				PED
	6. The two faces of an edge:		NFACE	PFACE
	7. The two vertices of an edge:		NVT		PVT
	8. The four wing edges of an edge:	NCW  PCW  NCCW  PCCW
~|---------------------------------------------------------------λ30;JUFA

	By constraining the arrangement of links in an edge node both
the  surface  orientataion  (interior  and  exterior)  and  a  linear
orientation of the edge as a directed vector can be  encoded. Viewing
an  edge of  an existing  polyhedron from  the exterior  side of  its
surface,  the links can  be arranged as illustrated  in figure (2.1).
Although the  vertices  in figure  (2.1) are  shown  with only  three
edges,  vertices may have  any number  of edges; the  other potential
edges would not be directly linked  to the middle edge of the  figure
and so  were  not shown.  To complete  the  representation, space  is
allocated  to contain the  3-D coordinates  of each vertex  in fields
named XWC,  YWC  and Further  important  (but not  fundamental)  data
fields  include, the  3-D perspective  projected coordinates  of each
vertex  with respect  to a camera  (one camera  at a  time) in fields
named XPP, YPP,  ZPP of vertex nodes.  Faces on the other  hand carry
exterior  pointing normal  vectors and  several words  of photometric
surface characteristics.  ZWC; the  initials  "WC" stand  for  <world
coordinates>. The face vectors are derived  from surface topology and
vertex  loci,  and  so  are  not  basic  geometric  data as  in  some
representations.
	
	The Winged  Edge polyhedron  representation as  presented  is
essentially complete. Edge  nodes carry most of  the topology, vertex
nodes carry  the geometry, face nodes carry photometry and body nodes
carry the semantics.  The point that  remains to be demonstrated,  is
that  the  appropriate subroutines  for  creating,   maintaining  and
exploiting edge orientation are are easily coded, execute efficiently
and provide  good primitives for  solving such geometric  problems as
hidden line elimination and polyhedral intersection.
[2.2	Perimeter Accessing.]

	The perimeter of a face is an ordered list of edges and vertices,
the perimeter of a vertex is an ordered list of edges and faces, and the
perimeter of an edge is an ordered list consisting of exactly two faces
and two vertices. The perimeter definitions are caricatured in figure (2.2).
One virtue of the winged edge representation is that the perimeters can be
traveled in either direction (clockwise or counter clockwise) and are always
maintained in order.

	Given one edge of  a face or vertex perimeter,  the next edge
clockwise  or  counter  clockwise  from  the  given  edge  about  the
particular face or  vertex can be retrieved  from the data  structure
with the assistance of two subroutines  called ECW and ECCW. The idea
of  the edge clocking routines  is to match the  given face or vertex
with one  of the faces  and vertices of  the given  edge and to  then
return the appropriate wing. One possible coding of ECCW and ECW might
be as follows:

~JAλ10;F.COMMENT FETCH EDGE COUNTER CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
	IF PFACE(E)=FV THEN RETURN(PCCW(E));
	IF NFACE(E)=FV THEN RETURN(NCCW(E));
	IF PVT(E)=FV   THEN RETURN(PCW(E));
	IF NVT(E)=FV   THEN RETURN(NCW(E));
	FATAL;
END "ECCW";

COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
	IF PFACE(E)=FV THEN RETURN(PCW(E));
	IF NFACE(E)=FV THEN RETURN(NCW(E));
	IF PVT(E)=FV   THEN RETURN(NCCW(E));
	IF NVT(E)=FV   THEN RETURN(PCCW(E));
	FATAL;
END "ECW";
~JUλ30;F.
	The first edge  of a face  or vertex is (of  course) directly
available from the  PED field of the face or vertex. For example, the
code fragment below can be used to visit all the edges of a face.

~JAλ10;F.COMMENT APPLY A FUNTION TO ALL THE EDGES OF A FACE;
BEGIN
	INTEGER F,E,E0;
	E←E0←PED(F);
	DO FUNCTION(E) UNTIL E0=(E←ECCW(E,F));
END;


Almost the same code fragment can be used to travel the perimeter of a vertex.


COMMENT APPLY A FUNTION TO ALL THE EDGES OF A VERTEX;
BEGIN
	INTEGER V,E,E0;
	E←E0←PED(V);
	DO FUNCTION(E) UNTIL E0=(E←ECCW(E,V));
END;
~JUλ30;F.
	Using the same idea as in the edge  clocking routines, a
face or vertex can  be retrieved relative to a given edge and a given
face or vertex. These routines include: FCW and FCCW which return the
face clockwise or counter clockwise from a given edge with respect to
a  given vertex;  VCW and  VCCW which  return the vetex  clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which return the face  or vertex of the given edge opposite the
given face or vertex.  Together the seven  routines: ECW, ECCW,  VCW,
VCCW, FCW,  FCCW  and OTHER exhaust the possible  oriented retrievals
from  an edge  node; they  also  alleviate the  need to ever explicitly
reference a wing field when traveling the surface of a polyhedron.

	With node type checking and signed arguments the seven perimeter
accessing routines could be replaced by a single routine perhaps named
PERIMETER_FETCH or PGET. On the otherhand, the type of arguments and
direction of access are almost always available at compile time so that 
the proliferation of accessing names allows for assembling in line code.


[2.3	Edge and Face Splitting.]

	Another simple virture  of the winged edge  representation is
that  edges and faces can  be split using  subroutines involving only
local alterations to the data  structure; likewise,  the splits  can
be easily removed. The reason for having the doubly linked rings is
for  the sake of rapid deletion of nodes from a body.
The edge  split routine,
ESPLIT, makes a new  edge and a new  vertex and places them  into the
surface  topology  as shown  in  figure  (2.3).  The kill  edge-vertex
routine, KLEV, undoes  an ESPLIT.   The  face split  routine,   MKFE,
creates a new  edge and a new face  and places them into  the surface
topology as  shown in figure (2.4); the  kill face-edge routine, KLFE,
undoes a MKFE.

FIGURES FOR ESPLIT & MKFE.
	VNEW ← ESPLIT(E);		E ← KLEV(VNEW);
	ENEW ← MKFE(V1,F,V2);		F ← KLFE(ENEW);


~JA;λ10;F.
INTEGER PROCEDURE ESPLIT (INTEGER E);
BEGIN "ESPLIT"
	INTEGER VNEW,ENEW,
COMMENT CREATE A NEW EDGE AND VERTEX ON THE BODY;
	VNEW ← MKV(E);
	ENEW ← MKE(E);
COMMENT CONNECT VERTICES AND FACES TO EDGES;
	PVT(ENEW) ← PVT(E);
	NVT(ENEW) ← VNEW;
	PVT(E) ← VNEW;
	PFACE(ENEW) ← PFACE(E);
	NFACE(ENEW) ← NFACE(E);
COMMENT CONNECT EDGES TO VERTICES;
	IF PED(V)=E THEN PED(V)←ENEW;
	PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
	NCW(ENEW) ← E; PCCW(ENEW) ← E;
	PCW(E) ← ENEW; PCCW(E) ← ENEW;
	WING(NCCW(E),ENEW);
	WING(PCW(E),ENEW);
	RETURN(VNEW);
END "ESPLIT";
~JU;λ30;F.

[2.4	Lowest Level Polyhedron Synthesis and Alteration.]

	This section concerns the details  of link manipulating which
are beneath the  Euler primitives explained in the next section. That
is the direct handling of links is not required of the  ordinary user
of winged  polyhedra, but is  discussed here  from the view  point of
implementation.  Internal  to  a modeling  system,  the  geometry and
topology  of   a  desired  polyhedron   becomes  available  in   some
non-standard format and a winged edge model is desired. Although bulk
conversion from an  alein external  polyhedron format  into a  winged
edge format is  occassionally important, the same details  apply when
altering an existing structure.
	In the  typical situation, there  are five steps:  first, get
the proper kinds of nodes into the body rings using the MKF, MKE, MKV
primitives. second, place the vertices by setting their XWC, YWC, ZWC
fields; third,  connect each vertex  and face  pointed to one  of its
edges  by setting their PED fields. fourth,  connect each edge to its
two faces and  its two vertices by  setting their NFACE, PFACE,  NVT,
PVT fields.  Finally, create the wing perimeter  pointers by applying
the WING primitive to pairs of edges to be mated.

~|---------------------------------------------------------λ10;JAFA
BOX ~JCFA LOWEST LEVEL WINGED EDGE ROUTINES.

 	MKB,MKF,MKE,MKV,MKFRAME.	Make B.F.E.V. nodes.
	WING,INVERT,EVERT		Make and change wing pointers.
	LINKED				Find if two entities are linked.
	ECW,ECCW			Edge fetching around F.V. perimeters.
	OTHER,VCW,VCCW,FCW,FCCW		Face/Vertex fetching from an edge.
	BDET,BATT,BGET			Body parts linking and body get.
~|----------------------------------------------------------λ30;JUFA

[2.5	Coordinate Free Polyhedron Representation.]

	As  in general  relativity,  all  geometric entities  can  be
represented  in a coordinate free  form.  In particular,   the vertex
coordinates of a  polyhedra can  be recovered from  edge lengths  and
dihedral angles  (the angle formed  by the  two faces at  each edge).
Having the  geometry carried by only two numbers per edge rather than
by three numbers per vertex does not necessarily yield a more concise
representation because  edges always outnumber vertices  two for one,
and in the case of a triangulated polyhedron edges outnumber vertices
by three to one.

	One application  of a  coordinate free representation  arises
when it is necessary to measure a complicated shape with simple tools
such as a caliper and straight edge. For example, one way to go about
recording the topology and geometry of an arbitrary object is to draw
a  triangulated  polyhedron  on  its  surface  with  serial  numbered
vertices and record  for each edge its  length, its two vertices  and
its "signed  dihedral length".   The dihedral length  is the distance
between the vertices  opposite the  edge in  each of  the edge's  two
triangles, the  length can  be given  a sign  convention to  indicate
whether the edge  is concave or convex.  The required dihedral angles
can then be computed from the signed dihedral lengths.